package algorithm.fibonacci;

public class FibonacciProblem {

    public static int f1(int n){
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2)
            return 1;
        return  f1(n - 1) + f1(n - 2);
    }

    public static int f2(int n){
        int[][] base = {{1, 1}, {1, 0}};
        int[][] res = matrixPower(base, n - 2);
        int[][] init = {{1, 1}};
        int[][] result = muliMatrix(init, res);
        return result[0][0];
    }

    public static long muli(int n, int m){
        int result = 1;
        int b = n;
        while(m != 0){
            if((m & 1) != 0){
                result = result * b;
            }
            b = b * b;
            m = m >> 1;
        }
        return result;
    }

    public static int[][] matrixPower(int[][] m, int p){
        int[][] result = new int[m.length][m[0].length];
        for (int i = 0; i < m.length; i++) {
            result[i][i] = 1;
        }
        int[][] a = m;
        while(p != 0){
            if((p & 1) != 0){
                result = muliMatrix(result, a);
            }
            p = p >> 1;
            a = muliMatrix(a, a);
        }
        return result;
    }

    public static int[][] muliMatrix(int m1[][], int m2[][]){

        int[][] result = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                int sum = 0;
                for (int k = 0; k < m1[0].length; k++) {
                    sum += m1[i][k] * m2[k][j];
                }
                result[i][j] = sum;
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        System.out.println(f1(5));
        System.out.println(f2(6));
        //1,1,2,3,5
//        System.out.println(muli(10, 5));
//        int[][] ints = muliMatrix(new int[][]{{1, 2}, {2, 3}}, new int[][]{{1, 2}, {2, 3}});
//        int[][] ints1 = matrixPower(new int[][]{{1, 2}, {2, 3}}, 2);
//        System.out.println();
    }
}
